package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 非递归遍历二叉树
 */
public class BiTree02_NoRecursiveTraversal {

    public static void main(String[] args) {
        List<Integer> nodes = Arrays.asList(3, 9, 20, null, null, 15, 7);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodes, 0);
        List<Integer> result = preorderTraversal(root);
        System.out.println(result);
    }

    /**
     * 非递归实现前序遍历：根左右，入栈顺序：根右左
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 根节点不为空则入栈
        stack.push(root);
        // 访问元素的顺序和处理元素的顺序是一致的，都是根节点
        while (!stack.isEmpty()) {
            // 处理根节点
            TreeNode node = stack.pop();
            result.add(node.val);
            // 右节点先入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            // 左节点后入栈
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }

    // 中序遍历：左根右
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 用栈来处理节点上的元素
        Stack<TreeNode> stack = new Stack<>();
        // 用指针来遍历节点
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }

    // 后序遍历：左右根
    public static List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 根节点不为空则入栈
        stack.push(root);
        // 在前序遍历上进行修改：根左右，更换左右节点遍历顺序 -> 根右左，翻转遍历结果-> 左右根
        while (!stack.isEmpty()) {
            // 处理根节点
            TreeNode node = stack.pop();
            result.add(node.val);
            // 左节点先入栈，后处理
            if (node.left != null) {
                stack.push(node.left);
            }
            // 右节点后入栈，先处理
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        // 翻转遍历结果
        Collections.reverse(result);
        return result;
    }

}
